#include <iostream>
#include <string>
#include <vector>
#include <numeric>

using namespace std;

class Solution {
public:
	int i = 0;
	string endS;
    string getPermutation1(int n, int k) {
		string s;

		for(int i = 1; i <= n; i++){
			s.push_back(i + '0');
		}
		back(s, n, 0, k);
		// for(auto i : res){
			// cout << i << endl;
		// }
		return endS;
    }
	
	void back(string s, int len, int index, int k){
		if(index == len){
			i++;
			cout << s << endl;
			if(i == k){
				endS = s;
			}
			return;
		}
		for(int i = index; i < len; i++){
			swap(s[i], s[index]);
			back(s, len, index + 1, k);
			swap(s[index], s[i]);
		}
	}
	

	/*
	// https://blog.csdn.net/ltrbless/article/details/87696372
	5,4,3,2,1 康托展开值 4*4! + 3*3! + 2*2! + 1*1! + 0*0!  4*24 + 3*6 + 2*2 + 1 + 0 = 119
	
	4,3,5,1,2 康托展开值 3*4! + 2*3! + 2*2! + 0*1! + 0*0!  3*24 + 2*6 + 2*2 + 0 + 0 = 88
	
	1423      康托展开值 0*3! + 2*2! + 0*1! + 0*0! = 4 
	
	
	这个写法的原形是借鉴了题解区的一个大神的。
然后我又优化了一些细节。。

大体思路：
因为全排列。按顺序排。开头肯定也是1开头的有多少个2 开头的也多少个3 开头的。。。这样。
1后面的是n-1的阶层个。=====这个规律奠定了这个解法的核心思路。
然后我们通过k和n-1阶乘之间的关系。来逐个的从头到尾的判断出每个位置的数字。。
	*/
	string getPermutation(int n, int k)
    {
        k--;
//题目给的k是第k个 也就是数量，我们要给他转成序列号k-1；
        int dp[n];
        dp[0] = 1;
        for (int i = 1; i < n; ++i){
			dp[i] = dp[i - 1] * i;
		}
            
//构建阶层数组dp 因为我们只需要用到n-1 阶层 所以这里dp只需要n个就行
        vector<int> nums(n);
        iota(nums.begin(), nums.end(), 1);
//构建1-n每个数字的数组nums 。到时候我们要一个个取出来转成string 然后从数组里清除掉。
        string s;
        while (n--)
        {
//第一次进入循环 这个n就已经是n-1了
            int ord = k / dp[n];
			cout << dp[n] << endl;
            s.push_back(nums[ord] + '0');
            for (int j = ord; j < n; ++j)
                nums[j] = nums[j + 1];
//这是数组最原始的删除一个位置元素的方式。
            k %= dp[n];
        }
        return s;
    }
	
	string getPermutation2(int n, int k){
		vector<int> dp(n);
		dp[0] = 1;
		for(int i = 1; i < n; i++){
			dp[i] = dp[i - 1] * i;
		}
		string s;
		vector<int> nums(n);
		iota(nums.begin(), nums.end(), 1);
		k--;
		for(int i = n-1; i >= 0; i--){
			int tmp = k / dp[i];
			s += nums[tmp] + '0';
			for(int j = tmp; j < i; ++j){
				cout << nums[j+1] << endl;
				nums[j] = nums[j+1];
			}
			k %= dp[i];
		}
		return s;
	}
};

int main(){
	Solution so;
	// 1423
	string s = so.getPermutation2(3, 3);

	cout << s << endl;
	return 0;
}